\section{Descripción del problema}

El \textbf{2DCSP} (\textit{Constrained Two-Dimensional Cutting Stock Problem} o
problema de Corte Bidimensional) se enuncia de la siguiente forma:

Se dispone de una superficie rectangular $S$ de dimensiones $L \times W$ que ha
de ser cortada en un conjunto de piezas más pequeñas utilizando cortes
ortogonales de guillotina: cualquier corte debe ir de lado a lado del
rectángulo y ser paralelo a una de las otras dos aristas.

Los rectángulos
obtenidos deben pertenecer a un conjunto dado de rectángulos o patrones
$D = \{ T_1 \dots T_n \}$ donde el $i$-ésimo patrón $T_i$ tiene dimensiones
$l_i \times w_i$ (véase la figura \ref{fig:surface-patterns}).

Cada patrón $T_i$ tiene asociado un beneficio $p_i$ y 
un límite de unidades $b_i$. El objetivo es encontrar un posible patrón
de corte con $x_i$ piezas de tipo $T_i$ que maximice el beneficio total.

\begin{displaymath}
\sum_{i=1}^{n} p_i x_i \mbox{  sujeto a  } x_i \le b_i
\end{displaymath}

\begin{figure}
  \centering
    \includegraphics[width=200pt]{images/surface-patterns.png}
  \caption{Representación de la superficie $S$ y los patrones $T_i$}
  \label{fig:surface-patterns}
\end{figure}

El problema del corte bidimensional tiene multitud de aplicaciones dentro de
distintas industrias. El material de la superficie sobre la que se
distribuirán las plantillas puede ser de diversos tipos: vidrio, metal,
tela o madera.

Se trata de un problema ampliamente estudiado, con una gran cantidad
de variantes, y que sigue teniendo a muchos investigadores trabajando
en él. Cabe destacar los trabajos de
\textit{Gilmore} y \textit{Gomory} \cite{Gil:Gom:66},
\textit{Viswanathan} y \textit{Bagchi} \cite{Bag:Vis:91}, y
\textit{Sweeney} y \textit{Paternoster} \cite{Pat:Swe}.

\newpage

\section{Resolución}

Existen numerosas formas de abordar el problema:

\begin{itemize}
\item Algoritmos de programación dinámica y variantes.
\item Métodos de programación entera. En este caso, uno de los algoritmos
más empleados es la ramificación y poda (\textit{Branch-and-Bound}).
\item Búsquedas heurísticas.
\item Aproximaciones mediante redes neuronales.
\item Aproximaciones mediante uso de sistemas expertos o sistemas basados
en el conocimiento.
\item Métodos que emplean paralelismo.
\end{itemize}

Gracias al trabajo de la compañera \textbf{Gara Miranda Valladares} he
podido disponer de una implementación brillante para la resolución de este
problema \cite{LeonMRS07}. Se trata de un algoritmo secuencial que
utiliza la técnica de \textit{Ramificación y Poda} apoyándose en una
heurística basada en \textit{Programación Dinámica} para obtener una
cota inferior que permita guiar la poda del árbol de posibles
subsoluciones.

Gracias a lo complejo del algoritmo, la cantidad de datos de interés para
el programador y la posibilidad de medir tiempos para dos soluciones
distintas (heurística y óptima), se podrá exprimir al máximo el módulo
\texttt{Bench::Test} y utilizar casi el 100\% de su funcionalidad.

\section{Instrumentación del programa}

Para que el módulo \texttt{Bench::Test} pueda realizar su labor
correctamente el programa del usuario debe estar instrumentado
de forma que todos los parámetros que le interesen sean
devueltos por el programa, ya sea volcando 
la salida en un fichero o mostrándola por pantalla
(\textit{Standard Output}). La instrumentación puede también 
automatizarse usando una herramienta adecuada \cite{call}.

El objeto \texttt{Bench::Test} lanza las ejecuciones y
obtiene la salida o la lee desde un fichero para
a continuación aplicar expresiones regulares que permitan
filtrar la información deseada. Por ello, a la hora
de instrumentar el programa se debe mostrar los
datos de forma que puedan ser fácilmente reconocidos
mediante una expresión regular.

En este problema, los valores que pueden ser interesantes
para el usuario de cara a programar posibles mejoras o analizar el
rendimiento de su implementación son los siguientes:

\begin{itemize}
\item Beneficio obtenido con la heurística
\item Tiempo que emplea la heurística
\item Nombre del problema
\item Valor de la cota superior
\item Número de nodos generados
\item Número de nodos computados
\item Beneficio de la solución óptima
\item Tiempo que emplea el algoritmo óptimo
\end{itemize}

No fue necesario realizar este paso
puesto que el programa ya estaba perfectamente instrumentado.
Véase una ejecución:

\begin{verbatim}
   $ ./cutting tests/cut2D.3.dat 
   Heuristic = 1840
   Heuristic Time: 0.040302
   
   Problem Name: tests/cut2D.3.dat
   Global Upper Bound: 2240
   Computed nodes : 1173
   Generated nodes: 1442
   Time: 0.375356
   Sequential Solution Value = 1860
\end{verbatim}

\section{Parámetros de configuración}

Una vez instrumentado el programa cliente se han de
definir los parámetros que guíen las ejecuciones. Como ya
se ha explicado anteriormente en esta memoria,
para ello existen dos posibilidades:

\begin{itemize}
\item 
Escribir un script Perl que cree un objeto de la clase
Bench::Test con los parámetros adecuados (Ver documentación
de la clase \texttt{Bench::Test} en el capítulo~\ref{chapter:Bench-Test})

\item 
Utilizar el script \texttt{maketest} proporcionado junto
con el modulo \texttt{Bench::Test} y definir los parámetros
mediante un fichero de configuración cuyo nombre, por defecto,
es \texttt{maketest.conf} (véase la documentación del script
\texttt{maketest} en el capítulo \ref{chapter:maketest})
\end{itemize}

La forma más sencilla para un usuario sin conocimientos
de Perl es escribir el fichero de configuración y hacer
uso del script proporcionado.

A continuación empezamos a escribir, paso a paso, el
fichero de configuración.

\section{Expresiones regulares}

La primera acción que realiza el objeto \texttt{Bench::Test}
después de cada ejecución es aplicar las expresiones
regulares sobre la salida generada por el programa
del usuario. Estas expresiones permiten filtrar valores de
salida en los que el usuario está interesado.

Para definirlas, se utiliza el array \texttt{@TABLE} y se
debe tener en cuenta el formato de salida del programa.

Como se vio antes, el resultado de una ejecución del
programa tiene un aspecto similar a éste:

\begin{verbatim}
   $ ./cutting tests/cut2D.3.dat 
   Heuristic = 1840
   Heuristic Time: 0.040302
   
   Problem Name: tests/cut2D.3.dat
   Global Upper Bound: 2240
   Computed nodes : 1173
   Generated nodes: 1442
   Time: 0.375356
   Sequential Solution Value = 1860
\end{verbatim}

Para filtrar dicha salida el array \texttt{@TABLE}
debería tener la siguiente forma:

\begin{verbatim}
   @TABLE = (
     OPT    => 'Sequential\s+Solution\s+Value\s*=\s*(\d+)', 
     HEUR   => 'Heuristic = (\d+)', 
     UPPER  => 'Global Upper Bound: (\d+)',
     GEN    => 'Generated\s+nodes\s*:\s*(\d+)',
     COMP   => 'Computed\s+nodes\s*:\s*(\d+)',
     INS    => 'Inserted\s+nodes\s*:\s*(\d+)',
     HTIME  => 'Heuristic\s+Time:\s*(.*)\n',
     TIME   => '\nTime:\s*(.*)\n',
     RATE  => sub {
                 my $output = shift;
                 $output =~ /Heuristic = (.*)\n(.|\n)*Value = (.*)\n/;
                 my $rate = 100 * $1 / $3;
                 return "$rate\%";
              }
   );
\end{verbatim}

Obsérvese que el array \texttt{@TABLE} está formado por
pares clave-valor cuya clave indica el nombre que el
usuario desea dar al campo objeto de estudio (no deben 
usarse los nombres \texttt{TEST} y \texttt{NAME} porque están
reservados) y cuyo valor puede ser de dos tipos:

\begin{description}

\item[{\textbf{Cadena de caracteres:}}] \mbox{}

Contiene la expresión regular que permite filtrar la salida.
Debe contar con una y sólo una parentización en el lugar donde
se encuentre el campo que queremos filtrar.

\item[{\textbf{Referencia a rutina:}}] \mbox{}

En lugar de aplicar una expresión regular sobre la salida
se deja al usuario la responsabilidad del filtrado. La rutina
recibe como parámetro la salida intacta del programa.
Esta opción es muy útil a la hora de combinar varios resultados
y devolver un solo campo.
\end{description}

En el ejemplo se utiliza una referencia a rutina para el campo
\texttt{RATE}. En dicha rutina se recoge el parámetro \texttt{\$output}
que contiene la salida de la ejecución, se le aplica una expresión
regular para filtrar los valores de beneficio de la heurística, y de
la solución óptima, y por último se devuelve el valor en porcentaje
de la \textit{tasa de acierto} o \textit{grado de acercamiento}
de la heurística con respecto a la solución óptima.

\section{Parámetros de ejecución}

Una vez definidas las expresiones regulares que filtrarán
la salida del programa, es hora de indicar los parámetros
de ejecución. El programa de este ejemplo recibe como único
parámetro el nombre de un fichero de texto que contiene la
descripción del problema. 

Suponiendo que los ficheros de datos con los problemas a resolver
se encuentran en un directorio aparte llamado \texttt{tests}, se define
el array \texttt{@TESTS} de la siguiente forma:

\begin{verbatim}
   @TESTS = (
     cut01 => 'tests/cut2D.1_.dat',
     cut02 => 'tests/cut2D.1.dat',
     cut03 => 'tests/cut2D.2_.dat',
     cut04 => 'tests/cut2D.2.dat',
     cut05 => 'tests/cut2D.3_.dat',
     cut06 => 'tests/cut2D.3.dat',
     cut07 => 'tests/cut2D.A1.dat',
     cut08 => 'tests/cut2D.A2.dat',
     cut09 => 'tests/cut2D.A3.dat',
     cut10 => 'tests/cut2D.A4.dat',
   );
\end{verbatim}

Esta definición generaría diez ejecuciones de la forma:

\begin{verbatim}
   $ <ejecutable>  tests/cut2D.1_.dat
   $ <ejecutable>  tests/cut2D.1.dat
   $ <ejecutable>  tests/cut2D.2_.dat
   $ <ejecutable>  tests/cut2D.2.dat
   $ <ejecutable>  tests/cut2D.3_.dat
   $ <ejecutable>  tests/cut2D.3.dat
   $ <ejecutable>  tests/cut2D.A1.dat
   $ <ejecutable>  tests/cut2D.A2_.dat
   $ <ejecutable>  tests/cut2D.A3.dat
   $ <ejecutable>  tests/cut2D.A4.dat
\end{verbatim}

Nótese que el array \texttt{@TESTS} está formado
por pares clave-valor. La clave indica el nombre
del test correspondiente. El nombre de este test estará
disponible al usuario como un campo llamado \texttt{NAME}
en la tabla final, como si hubiera sido definido en el
array \texttt{@TABLE}.

Si el programa de usuario sólo recibe un parámetro y ese parámetro
es un fichero (como en este caso), el módulo \texttt{Bench::Test}
dispone de una función (\texttt{get\_tests\_from\_glob}) que permite obtener
el array \texttt{@TESTS} mediante un \textit{glob} que represente a 
todos los ficheros de datos. En este caso:

\begin{verbatim}
   @TESTS = get_tests_from_glob('tests/*.dat');
\end{verbatim}


\section{Entornos de ejecución}

Todavía no se han definido en el fichero de configuración
los parámetros relacionados con el ejecutable y los entornos
de ejecución (máquinas remotas, conexiones). Para ello se utiliza
hash \texttt{\%EXPERIMENTS}.

El hash \texttt{\%EXPERIMENTS} está formado por pares clave-valor
cuyas claves son el nombre que el usuario quiere dar a
sus entornos de ejecución (por ejemplo el nombre de la máquina),
y cuyo valor es una referencia a un objeto de la clase
\texttt{Bench::Test::Base}, \texttt{Bench::Test::Local}
o \texttt{Bench::Test::Remote} (véase la documentación de
dichos módulos en los capítulos
\ref{chapter:Bench-Test-Base}, \ref{chapter:Bench-Test-Local} y 
\ref{chapter:Bench-Test-Remote}).

Para este ejemplo podríamos definir el hash \texttt{\%EXPERIMENTS} de
la siguiente forma:

\newpage

\begin{verbatim}
   %EXPERIMENTS = (
     'FEB_07' => Bench::Test::Base->new (
                    WORKDIR => 'FEB_07'
                 ),

     'LOCAL'  => Bench::Test::Local->new  (
                    WORKDIR   => '.',
                    EXECUTABLE => './cutting',
                 ),

     'ORION'  => Bench::Test::Remote->new (
                    HOST       => 'user@host',
                    WORKDIR    => '/home/user/cutting',
                    EXECUTABLE => 'cutting',
                    PREAMBLE   => \&my_preamble,
                    POSTAMBLE  => \&my_postamble,
                 ),
   );
\end{verbatim}

Esta definición contiene los tres posibles objetos: \texttt{Bench::Test::Base},
\texttt{Bench::Test::Local} y \texttt{Bench::Test::Remote}. La función de estos objetos
es definir los parámetros de ejecución en máquina local, remota o acceder
a resultados de ejecuciones anteriores previamente almacenadas.

\subsection{Objeto \texttt{Bench::Test::Base}}

El constructor de \texttt{Bench::Test::Base} recibe como único parámetro
el nombre del directorio en donde se encuentran
los ficheros con las salidas de las ejecuciones
(que fueron ejecutadas en el pasado) con las
que queremos comparar (\texttt{WORKDIR}).

El nombre del archivo a leer consiste en nombre del \texttt{test} definido
anteriormente en el array \texttt{@TESTS} seguido de la extensión
\texttt{.base} al final.

\subsection{Objeto \texttt{Bench::Test::Local}}

El objeto \texttt{Bench::Test::Local} se encarga de las ejecuciones en la 
máquina local. Su constructor recibe como parámetros la ruta al directorio
de trabajo donde se encuentra el fichero ejecutable (\texttt{WORKDIR})
y el nombre de dicho fichero (\texttt{EXECUTABLE}).

\subsection{Objeto \texttt{Bench::Test::Remote}}

El objeto \texttt{Bench::Test::Remote} permite las ejecuciones en máquinas
remotas. Su constructor recibe como parámetros el nombre del host
(y usuario, si hiciera falta) donde se van a lanzar las ejecuciones.
También recibe la ruta al directorio de trabajo y el nombre del
fichero ejecutable en la máquina remota.

Si el directorio de trabajo no existe o el ejecutable no se encuentra en
la máquina remota, pueden definirse dos parámetros (\texttt{PREAMBLE} y
\texttt{POSTAMBLE}) que permiten al usuario subir archivos y ejecutar
comandos en dicha máquina. Se trata de dos referencias a rutina
que reciben como parámetro una referencia al objeto
\texttt{GRID::Machine} con el que se ha establecido la conexión con
la máquina remota.

El módulo \texttt{GRID::Machine} \cite{CasianoGridMachineDoc}
permite subir archivos y ejecutar comandos
en la máquina remota con la que ha establecido conexión a traves
de SSH. Véase el apéndice ``\textit{El módulo} \texttt{GRID::Machine}''
en el capítulo \ref{chapter:GRID-Machine}.

En el ejemplo los valores de \texttt{PREAMBLE} y \texttt{POSTAMBLE} apuntan
respectivamente a las rutinas \texttt{my\_preamble} y \texttt{my\_postamble} que 
el usuario debe definir en el fichero de configuración. A continuación una
posible definición de estas dos rutinas:

\begin{verbatim}
   sub my_preamble {
      my $machine = shift;
      $machine->put(['cutting.tar.gz']);
      $machine->tar('cutting.tar.gz', '-xz')->ok
         or die 'Error trying to extract cutting.tar.gz';
      $machine->chdir('cutting');
      $machine->system('make');
   };

   sub my_postamble {
      my $machine = shift;
      $machine->chdir('..');
      $machine->system('rm -rf cutting');
      $machine->system('rm cutting.tar.gz');
   }
\end{verbatim}

En la rutina \texttt{my\_preamble} se toma el objeto \texttt{\$machine} de la
clase \texttt{GRID::Machine} y se utilizan los siguientes métodos:

\begin{itemize}
\item \texttt{put}: para enviar el archivo comprimido 
\texttt{cutting.tar.gz} que contiene el código fuente del programa.
\item \texttt{tar}: para descomprimir el archivo.
\item \texttt{chdir}: para cambiar al directorio de trabajo
\item \texttt{system}: para ejecutar la orden \texttt{make} y compilar el programa.
\end{itemize}

Con estos cuatro pasos, se puede automatizar la preparación del entorno de ejecución
en cada máquina remota que se defina.

En la rutina \texttt{my\_postamble} se vuelven a utilizar los métodos \texttt{chdir} para
cambiar de directorio y \texttt{system} para ejecutar comandos shell y poder borrar
los archivos subidos con la orden \texttt{rm}.

\subsection{Otros parámetros en los constructores}

A parte de los parámetros descritos en el apartado anterior, se pueden
definir dos parámetros más para los objetos de las clases \texttt{Bench::Test::Local}
y \texttt{Bench::Test::Remote}:

\begin{description}
\item[{\texttt{OUTPUTFILE:}}] \mbox{}

Es posible que el programa del usuario vuelque la
salida sobre un fichero en lugar de mostrarla por pantalla. Este parámetro indica
la ruta a dicho fichero.
\item[{\texttt{BASEDIR:}}] \mbox{}

Indica el directorio donde se almacenarán los resultados
de las ejecuciones cuando se utilice el script \texttt{createtests}
(Véase la documentación del script en el capítulo \ref{chapter:createtests}).

\end{description}

\section{Validez de los tests}

Cada ejecución realizada genera un campo llamado \texttt{TEST} que
indica si el test es válido (\textit{ok}) o no válido (\textit{Fail}).
El usuario puede indicar la condición de validez de un test mediante la
rutina \texttt{Bench::Test::Entry::is\_ok}. Esta rutina recibe como
parámetro el objeto de la clase \texttt{Bench::Test::Entry} asociado al
test en cuestión. Este objeto tiene disponibles todos los valores
de los campos definidos por el usuario en el array \texttt{@TABLE} y
algunos otros métodos muy útiles. Véase la documentación del módulo
\texttt{Bench::Test::Entry} en el capítulo \ref{chapter:Bench-Test-Entry}.

Un test se considera válido cuando la rutina \texttt{Bench::Test::Entry::is\_OK}
devuelve un valor verdadero. Si no fuera vital validar las ejecuciones, el usuario
podría escribir la rutina de forma que el resultado siempre fuese
válido:

\begin{verbatim}
   sub Bench::Test::Entry::is_OK {
      return 1;
   }
\end{verbatim}

En este caso se podría considerar que el resultado de una ejecución es válido
si se cumple que:

\begin{itemize}
\item Si el valor de beneficio óptimo obtenido (campo \texttt{OPT}) es el 
mismo que el que se obtuvo en una ejecución anterior que sirva como base.

\item Si el valor de beneficio óptimo (\texttt{OPT}) es mayor o igual que
el valor de beneficio heurístico (\texttt{HEUR}). El caso contrario sería
erróneo.
\end{itemize}

Por comodidad, y por no disponer de una primera versión \textit{estable} y
comprobada, se escogerá la segunda opción. La rutina quedaría así:

\newpage
\begin{verbatim}
   sub Bench::Test::Entry::is_OK { 
      my $entry = shift;

      my $opt = $self->get_field_value('OPT');
      my $heu = $self->get_field_value('HEUR');
 
      return $opt >= $heu;
   }
\end{verbatim}

La rutina anterior sigue estos pasos:

\begin{enumerate}
\item Recoge como parámetro el objeto \texttt{Bench::Test::Entry} asociado
a la ejecución en cuestión.
\item Recoge el valor del campo \texttt{OPT} gracias al método \texttt{get\_field\_value}.
\item Recoge el valor del campo \texttt{HEUR} gracias al método \texttt{get\_field\_value}.
\item Devuelve el resultado de la comprobación \texttt{OPT >= HEU}.
\end{enumerate}

\section{¿Qué campos mostrar?}

Es posible que en algún momento se necesite decidir si ver u ocultar alguno
de los campos que hemos especificado en el array \texttt{@TABLE}. Para
ello hacemos uso del array \texttt{@VISUAL}.

El array \texttt{@VISUAL} contiene una lista con los nombres de los
campos que queremos que aparezcan en la tabla final de resultados de la
siguiente tanda de ejecuciones. \texttt{@VISUAL} es un subconjunto de
los nombres de \texttt{@TABLE}. Véase un ejemplo:

\begin{verbatim}
   @VISUAL = (
              'TEST',
              'NAME',
              'GEN',
              'COMP',
              'OPT',
              'HEUR',
              'UPPER',
              'HTIME',
              'TIME',
              'RATE'
             );
\end{verbatim}

Otra forma más cómoda de escribir el array \texttt{@VISUAL} es
utilizar el operador \texttt{qw} de Perl:

\begin{verbatim}
   @VISUAL = qw(TEST NAME GEN COMP OPT HEUR UPPER HTIME TIME RATE);
\end{verbatim}

En este caso se estaría indicando que se desea mostrar
si el test es valido (\texttt{TEST}), el nombre del test (\texttt{NAME}), 
el número de nodos generados y computados (\texttt{GEN} y \texttt{COMP}), 
el valor de la solución óptima (\texttt{OPT}), el valor de la solución
heurística (\texttt{HEUR}), el valor de cota superior (\texttt{UPPER}),
el tiempo empleado por la heurística (\texttt{HTIME}), el tiempo del algoritmo
completo (\texttt{TIME}), y la \textit{tasa de acierto} de la heurística
respecto del algoritmo completo (\texttt{RATE}).

Además de indicar qué campos mostrar, el array \texttt{@VISUAL} es
usado para definir el orden en el que aparecerán dichos campos.

\section{Campos invariables}

Muchas veces ocurre que el valor de algunos campos es independiente
del lugar donde se realizan las ejecuciones. Para este caso, 
los valores de beneficio de la heurística y del algoritmo
completo, el valor de cota superior, y el número de nodos generados,
computados e insertados no varían con respecto a la máquina en
la que se ejecuta, ya que se trata del mismo algoritmo.

Para evitar que se muestren estos valores repetidos para cada una de
las máquinas, se incluyen dichos campos en el array \texttt{@UNIQUE}:

\begin{verbatim}
   @UNIQUE = qw(OPT HEUR UPPER GEN COMP INS RATE);
\end{verbatim}

Esto hace que en las tablas producidas durante la ejecución
sólo haya una columna \verb|OPT|, pese a que todas las ejecuciones
produzcan un campo \verb|OPT|.

Para ver la diferencia entre incluir o no incluir un campo
en el array \texttt{@UNIQUE}, se muestra un ejemplo:

Supongamos que el array \texttt{@VISUAL} está formado por
las claves \texttt{TEST}, \texttt{NAME} y  \texttt{OPT}:

\begin{verbatim}
   @VISUAL = qw(TEST NAME OPT);
\end{verbatim}

Si el campo \verb|OPT| se encuentra en el array \texttt{@UNIQUE},
la tabla de salida contendría un solo campo \texttt{OPT}:

\begin{verbatim}
   $ maketest
   TEST  NAME   OPT   
   ok    cut01  144   
   ok    cut02  244   
   ok    cut03  2778  
   ok    cut04  2892
   ok    cut05  2721
   ok    cut06  1860
\end{verbatim}

Si no se incluyese el campo \verb|OPT|, se generarían tres campos
llamados \verb|OPT(FEB_07)|, \verb|OPT(LOCAL)| y \verb|OPT(ORION)|,
aunque su valor sería el mismo:

\begin{verbatim}
   $ maketest
   TEST  NAME   OPT(FEB_07)  OPT(LOCAL)  OPT(ORION)  
   ok    cut01  144          144         144         
   ok    cut02  244          244         244         
   ok    cut03  2778         2778        2778        
   ok    cut04  2892         2892        2892        
   ok    cut05  2721         2721        2721        
   ok    cut06  1860         1860        1860        
\end{verbatim}

\section{¿En qué máquinas ejecutar?}

Al igual que con los campos filtrados y el array \texttt{@VISUAL}, también
sería deseable poder evitar que se realicen ejecuciones en ciertas máquinas aunque
estén definidas en el hash \texttt{\%EXPERIMENTS}.

Para ello, en
el array \texttt{@SELECTED} se indican los nombres de los \texttt{EXPERIMENTS}
en los que se desea realizar las ejecuciones. Por ejemplo:

\begin{verbatim}
   @SELECTED = qw(FEB_07 LOCAL ORION);
\end{verbatim}

Al incluir todos los \texttt{EXPERIMENTS}, se realizarán las ejecuciones en
todas las máquinas definidas anteriormente. Si se quisiese
no ejecutar en la máquina remota, el array \texttt{@SELECTED} tendría la
siguiente forma:

\begin{verbatim}
   @SELECTED = qw(FEB07 LOCAL);
\end{verbatim}

\section{Formato de salida}

Por último, sólo queda definir el formato de salida con el 
array \texttt{@OUTPUTFORMAT}. Véase un ejemplo:

\begin{verbatim}
   @OUTPUTFORMAT = (
      'text'          => 'output.txt',
      'html'          => 'output.html',
      'latex'         => 'output.tex',
      'xml'           => 'output.xml',
   );
\end{verbatim}

Se trata de un hash cuyas claves indican el formato en el
que se quiere la salida y cuyo valor especifica el fichero
a donde se debe enviar la salida con dicho formato. Si se deja
el valor en blanco la salida se muestra por pantalla.

Los formatos disponibles son \texttt{text} (texto plano), \texttt{xml},
\texttt{html} y \texttt{latex}. Además es posible que el usuario provea
un nuevo formato mediante la clave \texttt{file:fichero.tt} donde
\texttt{fichero.tt} es el nombre del fichero en el que el usuario
ha escrito su plantilla con Template Toolkit (Ver
documentación de Template Toolkit \cite{PerlTemplateToolkit}).

Para poder formatear la salida se debe esperar hasta que
se realice la última ejecución. Sin embargo,
se muestran por pantalla línea a línea los resultados de
cada ejecución formateados con simples tabuladores.

\newpage

\section{Fichero de configuración}

El fichero de configuración quedaría como sigue:

\begin{verbatim}
   @TABLE = (
     OPT    => 'Sequential\s+Solution\s+Value\s*=\s*(\d+)', 
     HEUR   => 'Heuristic = (\d+)', 
     UPPER  => 'Global Upper Bound: (\d+)',
     GEN    => 'Generated\s+nodes\s*:\s*(\d+)',
     COMP   => 'Computed\s+nodes\s*:\s*(\d+)',
     INS    => 'Inserted\s+nodes\s*:\s*(\d+)',
     HTIME  => 'Heuristic\s+Time:\s*(.*)\n',
     TIME   => '\nTime:\s*(.*)\n',
     RATE  => sub {
                 my $output = shift;
                 $output =~ /Heuristic = (.*)\n(.|\n)*Value = (.*)\n/;
                 my $rate = 100 * $1 / $3;
                 return "$rate\%";
              }
   );
\end{verbatim}

\begin{verbatim}
   @TESTS = (
     cut01 => 'tests/cut2D.1_.dat',
     cut02 => 'tests/cut2D.1.dat',
     cut03 => 'tests/cut2D.2_.dat',
     cut04 => 'tests/cut2D.2.dat',
     cut05 => 'tests/cut2D.3_.dat',
     cut06 => 'tests/cut2D.3.dat',
     cut07 => 'tests/cut2D.A1.dat',
     cut08 => 'tests/cut2D.A2.dat',
     cut09 => 'tests/cut2D.A3.dat',
     cut10 => 'tests/cut2D.A4.dat',
   );
\end{verbatim}

\begin{verbatim}
   sub my_preamble {
      my $machine = shift;
      $machine->put(['cutting.tar.gz']);
      $machine->tar('cutting.tar.gz', '-xz');
      $machine->chdir('cutting');
      $machine->system('make');
   };

   sub my_postamble {
      my $machine = shift;
      $machine->chdir('..');
      $machine->system('rm -rf cutting');
      $machine->system('rm cutting.tar.gz');
   }
\end{verbatim}

\begin{verbatim}
   %EXPERIMENTS = (
     'FEB_07' => Bench::Test::Base->new (
                    WORKDIR => 'FEB_07'
                 ),

     'LOCAL'  => Bench::Test::Local->new  (
                    WORKDIR   => '.',
                    EXECUTABLE => './cutting',
                 ),

     'ORION'  => Bench::Test::Remote->new (
                    HOST       => 'user@host',
                    WORKDIR    => '/home/user/cutting',
                    EXECUTABLE => 'cutting',
                    PREAMBLE   => \&my_preamble,
                    POSTAMBLE  => \&my_postamble,
                 ),
   );
\end{verbatim}

\begin{verbatim}
   sub Bench::Test::Entry::is_OK {
       my $self = shift;

       my $opt = $self->get_field_value('OPT');
       my $heu = $self->get_field_value('HEUR');
 
      return $opt > $heu;
   }
\end{verbatim}

\begin{verbatim}
   @VISUAL   = qw(TEST NAME GEN COMP OPT HEUR UPPER HTIME TIME RATE);
   @UNIQUE   = qw(OPT HEUR UPPER GEN COMP INS RATE);
   @SELECTED = qw(FEB_07 LOCAL ORION);
\end{verbatim}

\begin{verbatim}
   @OUTPUTFORMAT = (
      'text'          => 'output.txt',
      'html'          => 'output.html',
      'latex'         => 'output.tex',
      'xml'           => 'output.xml',
   );
\end{verbatim}

\newpage

\section{Resultado}

Para mayor comodidad supongamos que en el fichero de configuración
se han definido los arrays \texttt{@VISUAL} y \texttt{@SELECTED} de
la siguiente forma:

\begin{verbatim}
   @VISUAL   = qw(TEST NAME RATE TIME);
   @SELECTED = qw(LOCAL ORION);
\end{verbatim}

De esta forma se muestra información sobre el tiempo de ejecución
y de la tasa de acercamiento de la heurística respecto del
algoritmo completo. Además, solo se comparan las ejecuciones
en máquina local y en la máquina remota \verb|ORION|.

Gracias a esta reducción del número de campos que se visualizan
y de las máquinas en donde se llevan a cabo las ejecuciones 
se obtendrán tablas de datos más cortas y se podrá apreciar con más
detalle todos los formatos en los que se obtiene la salida.

Una ejecución del script \texttt{maketest} con el fichero de configuración
anteriormente descrito daría como resultado algo como:

\begin{small}
\begin{verbatim}
   $ maketest 
   TEST    NAME    RATE(LOCAL)     RATE(ORION)  TIME(LOCAL)  TIME(ORION)
   ok      cut01    97.2%   97.2%  0.386975     0.251727
   ok      cut02    98.4%   98.4%  0.001214     0.000458
   ok      cut03   100.0%  100.0%  0.007742     0.005901
   ok      cut04   100.0%  100.0%  0.028823     0.021571
   ok      cut05   100.0%  100.0%  0.000069     0.000071
   ok      cut06    98.9%   98.9%  0.385762     0.245468
   ok      cut07    95.0%   95.0%  0.086240     0.151367
   ok      cut08    97.2%   97.2%  7.338252     5.606661
   ok      cut09   100.0%  100.0%  0.054635     0.045010
   ok      cut10    99.0%   99.0%  0.161601     0.136388
\end{verbatim}
\end{small}

Esta tabla se va generando línea a línea, ejecución tras ejecución,
para que el usuario disponga de una respuesta rápida, aunque sea
sin formato.

Los demás formatos son volcados sobre los distintos ficheros
especificados en el array \texttt{@OUTPUTFORMAT}.

\subsection{Formato \texttt{text}}

Es el formato más simple de los cuatro formatos disponibles.
Devuelve los resultados como texto plano correctamente alineados.
Puede ser muy útil para trabajar con paquetes matemáticos
como \textbf{Octave} \cite{octave} o \textbf{Matlab} \cite{matlab},
o el paquete estadístico \textbf{R} \cite{R}.

El contenido del fichero \texttt{output.txt} obtenido de las ejecuciones
anteriores es el siguiente:


\begin{small}
\begin{verbatim}
   $ cat output.txt
   TEST  NAME   RATE    TIME(LOCAL)  TIME(ORION)  
   ok    cut01   97.2%  0.386975     0.251727     
   ok    cut02   98.4%  0.001214     0.000458     
   ok    cut03  100.0%  0.007742     0.005901     
   ok    cut04  100.0%  0.028823     0.021571     
   ok    cut05  100.0%  0.000069     0.000071     
   ok    cut06   98.9%  0.385762     0.245468     
   ok    cut07   95.0%  0.086240     0.151367     
   ok    cut08   97.2%  7.338252     5.606661     
   ok    cut09  100.0%  0.054635     0.045010     
   ok    cut10   99.0%  0.161601     0.136388     
\end{verbatim}
\end{small}

\subsection{Formato \texttt{xml}}

\textbf{XML} no nació sólo para su aplicación en Internet, sino que se propone como un estándar para
el intercambio de información estructurada entre diferentes plataformas. Se puede usar en bases
de datos, editores de texto, hojas de cálculo y casi cualquier cosa imaginable. Es por ello que
podría ser muy útil guardar los datos con este formato.

La estructura de formato que se propone consta de un elemento raíz \texttt{data} que contiene
un elemento \texttt{entry} por cada ejecución realizada. La información asociada a dichas ejecuciones se
guarda en atributos cuyos nombres coinciden con el nombre de los campos generados. Véase
el resultado de las ejecuciones anteriores en formato XML:

\begin{tiny}
\begin{verbatim}
   $ cat output.xml
   <?xml version="1.0" encoding="ISO-8859-1" ?>
   <data>
      <entry test="ok" name="cut01" rate=" 97.2%" time_local="0.386975" time_orion="0.251727" />
      <entry test="ok" name="cut02" rate=" 98.4%" time_local="0.001214" time_orion="0.000458" />
      <entry test="ok" name="cut03" rate="100.0%" time_local="0.007742" time_orion="0.005901" />
      <entry test="ok" name="cut04" rate="100.0%" time_local="0.028823" time_orion="0.021571" />
      <entry test="ok" name="cut05" rate="100.0%" time_local="0.000069" time_orion="0.000071" />
      <entry test="ok" name="cut06" rate=" 98.9%" time_local="0.385762" time_orion="0.245468" />
      <entry test="ok" name="cut07" rate=" 95.0%" time_local="0.086240" time_orion="0.151367" />
      <entry test="ok" name="cut08" rate=" 97.2%" time_local="7.338252" time_orion="5.606661" />
      <entry test="ok" name="cut09" rate="100.0%" time_local="0.054635" time_orion="0.045010" />
      <entry test="ok" name="cut10" rate=" 99.0%" time_local="0.161601" time_orion="0.136388" />
      <entry test="ok" name="cut11" rate="100.0%" time_local="1.128277" time_orion="0.879753" />
      <entry test="ok" name="cut12" rate=" 92.7%" time_local="0.129981" time_orion="0.142284" />
   </data>
\end{verbatim}
\end{tiny}

\subsection{Formato \texttt{html}}

El formato \textbf{HTML} puede ser útil si el trabajo que se está realizando ha
de ser publicado en Internet. En la figura~\ref{fig:outputhtml2} se muestra
el contenido del fichero \texttt{output.html} abierto en un navegador.

\begin{figure}{h!}
  \centering
    \includegraphics[width=\textwidth]{images/outputhtml2.png}
  \caption{Salida en formato HTML vista en un navegador}
  \label{fig:outputhtml2}
\end{figure}

\subsection{Formato \texttt{latex}}

Para un investigador es muy útil obtener los resultados en formato \textbf{\LaTeX}
de forma que sea instantánea la inclusión de dichos resultados en el próximo
artículo que esté escribiendo. Para ello bastaría con incluir en su
fichero \texttt{.tex} una línea con la orden: \verb!\input{output.tex}!.

Y tendría automáticamente incluida una tabla final de datos como la mostrada
en el cuadro~\ref{table:outputlatex}.

\begin{table}
\begin{center}
\begin{tabular}{|ccccc|}
\hline
TEST & NAME & RATE & TIME(LOCAL) & TIME(ORION)\\
\hline
ok & cut01 &  97.2\% &  0.386975 & 0.251727\\
\hline
ok & cut02 &  98.4\% &  0.001214 & 0.000458\\
\hline
ok & cut03 & 100.0\% &  0.007742 & 0.005901\\
\hline
ok & cut04 & 100.0\% &  0.028823 & 0.021571\\
\hline
ok & cut05 & 100.0\% &  0.000069 & 0.000071\\
\hline
ok & cut06 &  98.9\% &  0.385762 & 0.245468\\
\hline
ok & cut07 &  95.0\% &  0.086240 & 0.151367\\
\hline
ok & cut08 &  97.2\% &  7.338252 & 5.606661\\
\hline
ok & cut09 & 100.0\% &  0.054635 & 0.045010\\
\hline
ok & cut10 &  99.0\% &  0.161601 & 0.136388\\
\hline
\end{tabular}
\end{center}
\caption{Tabla generada con \texttt{Bench::Test}}
\label{table:outputlatex}
\end{table}

\newpage

\subsection{Otros formatos: el formato \texttt{file}}

Si los cuatro formatos anteriores no son suficiente o se desea personalizar
aún más la salida, el usuario tiene la posibilidad de escribir una plantilla
utilizando Template Toolkit \cite{TT}. La forma de especificar la nueva plantilla
es, como se mencionó antes, la siguiente:

\begin{verbatim}
   @OUTPUTFORMAT = (
      'file:miplantilla.tt' => 'outputfile'
   );
\end{verbatim}

El único aspecto que debe conocer el usuario al escribir la plantilla es que
los datos se encuentran en la variable \texttt{data} y que dicha variable se trata de un
\textit{array de arrays} que contiene todos los valores
obtenidos en las ejecuciones.

Véase un ejemplo de plantilla:

\begin{verbatim}
   $ cat miplantilla.tt 
   [% FOREACH row IN data -%]
   Row: [ 
   [%- FOREACH item IN row -%]$item [%- END -%]
   ]
   [% END -%]
\end{verbatim}

Con esta plantilla se obtendría un resultado como este:

\begin{verbatim}
   $ cat outputfile
   Row: [ TEST NAME RATE TIME(LOCAL) TIME(ORION) ]
   Row: [ ok cut01  97.2% 0.390414 0.309255 ]
   Row: [ ok cut02  98.4% 0.001208 0.000451 ]
   Row: [ ok cut03 100.0% 0.012183 0.005965 ]
   Row: [ ok cut04 100.0% 0.028402 0.021579 ]
   Row: [ ok cut05 100.0% 0.000063 0.000066 ]
   Row: [ ok cut06  98.9% 0.308219 0.246017 ]
   Row: [ ok cut07  95.0% 0.086591 0.069746 ]
   Row: [ ok cut08  97.2% 7.176788 8.776497 ]
   Row: [ ok cut09 100.0% 0.055091 0.045222 ]
   Row: [ ok cut10  99.0% 0.161295 0.137805 ]
\end{verbatim}
